/*
 *Description:
 *User:laoHu
 *Created with Intellij IDEA 2025
 *Data:2025.05.00
 *Time:00:00
 */
public class SingleNode {

    //链表的结点的两个变量值

    public int val;

    public SingleNode next;



    //构造方法

    public SingleNode() {

    }



    public SingleNode(int val) {

        this.val = val;

    }



    //重写toString方法

    @Override

    public String toString() {

        return val + " " + ((next != null) ? next : "") ;



    }



    //头节点引用

    public SingleNode head;



    //节点的构造：调用方法创建5个节点

    public  void creatNode(){



        SingleNode node1 = new SingleNode(12);

        SingleNode node2 = new SingleNode(23);

        SingleNode node3 = new SingleNode(34);

        SingleNode node4 = new SingleNode(45);

        SingleNode node5 = new SingleNode(56);



        //赋值节点值:1 -> 2 -> 3 -> 4 -> 5

        head = node1;

        node1.next = node2;

        node2.next = node3;

        node3.next = node4;

        node4.next = node5;



    }



    //打印节点的值

    public void display(){

        SingleNode cur = head;

        System.out.print(this.getClass() + " = [");

        while(cur != null){

            if(cur.next != null)

                System.out.print(cur.val + ",");

            else

                System.out.print(cur.val);

            cur = cur.next;

        }

        System.out.println("]");

    }



    //头插法：在头部位置增加节点

    public void firstAddNode(int val){

        //1.创建一个节点对象

        SingleNode node = new SingleNode(val);

        //2.将创建的节点的next赋值为head

        node.next = this.head;

        //3.将head赋值为node

        this.head = node;

    }



    //尾插法：在末尾加入一个节点

    public void lastAddNode(int val){

        //1.创建一个节点

        SingleNode node = new SingleNode(val);

        //2.没有元素

        if(this.size() == 0){

            head = node;

        }

        //3.存在元素

        //3.1查找最有一个元素

        SingleNode cur = head;

        while(cur.next != null){

            cur = cur.next;

        }

        //该节点的next

        cur.next = node;

    }



    //检测位置是否合法

    private boolean checkPosWhetherLegal(int pos){

        if(pos < 0 || pos > size()) return true;

        return false;

    }



    //指定位置前插入节点

    public void insertBefore(int pos,int val){

        //1.检查位置是否合法

        if(checkPosWhetherLegal(pos));

            //throw new PosException("位置非法，不可在此位置前插入：" + pos);

        //2.头插

        if(pos == 0)

            this.firstAddNode(val);

        //3.尾插

        if(pos == size())

            this.lastAddNode(val);

        //4，中间插入

        SingleNode node = new SingleNode(val);

        //查找前一个元素

        SingleNode cur = head;

        for (int i = 1; i < pos; i++) {

            cur = cur.next;

        }

        //赋值

        node.next = cur.next;

        cur.next = node;

    }



    //删除首次的出现元素

    public void remove(int val){

        SingleNode cur = head.next;

        SingleNode tem = head;



        if(size() == 0){

            System.out.println("链表节点为空，不可移除！");

            return;

        }

        if(size() == 1 && head.val == val){

            head = null;

        }

        if(size() != 1 && head.val == val){

            head = head.next;

        }

        //循环遍历

        while(cur != null){

            //找到了，移除

            if(cur.val == val && cur.next == null){

                tem.next = null;

                return;

            }

            if(cur.val == val){

                tem.next = cur.next;

                return;

            }

            tem = tem.next;

            cur = cur.next;

        }

    }



    //将指定元素全部删除

    public void allRemove(int val){

        SingleNode cur = head;

        while(cur != null){

            if(cur.val == val){

                remove(val);

            }

            cur = cur.next;

        }

    }



    //求节点的个数大小

    public  int size(){

        int count = 0;

        SingleNode cur = head;

        while(cur != null){

            count++;

            cur = cur.next;

        }

        return count;

    }



    //判断是否存在某个元素

    public boolean contain(int val){

        SingleNode cur = head;

        while(cur != null){

            if(cur.val == val) return true;

            cur = cur.next;

        }

        return false;

    }

    //回收链表

    public void clear(){

        head = null;

    }

    public SingleNode partition(int x) {
        //1。定义分段
        SingleNode bs = null;
        SingleNode be = null;
        SingleNode as = null;
        SingleNode ae = null;

        SingleNode cur = head;

        //2.遍历链表
        while(cur != null){
            //小于x
            if(cur.val < x){
                //首次添加
                if(bs == null){
                    bs = be = cur;
                }
                //非首次添加
                else{
                    be.next = cur;
                    be = be.next;
                }
            }
            //大于x
            else{
                //首次添加
                if(as == null){
                    as = ae = cur;
                }
                //非首次添加
                else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            //cur++
            cur = cur.next;
        }
        //考虑特殊情况：没有小于x的节点
        if(bs == null){
            return as;
        }

        if(ae.next != null){
            ae.next = null;
        }
        //拼接：be - as
        be.next = as;

        //返回值
        return bs;
    }

    //获取倒数第K个元素
    public int last_K_Node(int k){

        //快慢双指针
        SingleNode slow = head;
        SingleNode fast = head;

        //先使fast走k - 1步，k - 1为slow与fast间隔
        int cnt = 0;
        while(cnt != k - 1){
            fast = fast.next;
            cnt++;
        }
        //循环遍历
        while(fast.next != null){
           fast = fast.next;
           slow = slow.next;
        }
        return slow.val;
    }
}
